Zajęcia opisane niżej wymagają dodatkowo oprogramowania: Logo Komeniusz lub Logomocja, Eli. Na zajęciach zostanie wykorzystana także prezentacja multimedialna wykonana przez nauczyciela w programie PowerPoint Pt „Algorytm Euklidesa”.
ALGORYTM NWD / NAJWIĘKSZEGO WSPÓLNEGO DZIELNIKA /SPOSOBEM EUKLIDESA
Przygotowanie uczniów: • uczen umie wyjasnic pojecia: algorytm, algorytmika; • zna krótki rys historyczny budowania algorytmów na przestrzeni wieków; • umie podac kilka przykladów prostych algorytmów (z zycia) w postaci opisu slownego /lista kroków/; • umie wyróznic podstawowe etapy na drodze „ od problemu do wyniku”; • systematycznie i dokladnie prowadzic dzialania w prezentowaniu algorytmów za pomoca schematów blokowych . Przebieg zajec: I. Czesc wstepna: • Powitanie z uczniami. • Sprawdzenie listy obecnosci. • Nawiazanie do tematu zajec / uczniowie otrzymuja polecenie od nauczyciela, aby wyszukali w Internecie informacje na temat „Kim byl Euklides ?” i zrobili notatke z tych informacji w edytorze tekstu Word, a nastepnie ja zaprezentowali slownie (mozna tu zaproponowac uczniom strony, na których maja szukac informacji np.www.szkoly.edu.pl/gim.margonin/starozyt/euklid.htm, www.matematyka.prx.pl/strona/biografie/euklides.htm )/. II. Czesc wlasciwa: • Nauczyciel podaje pewna pare liczb; • Uczniowie odpowiadaja na pytania: - jaki jest ich najwiekszy dzielnik? - jakie liczby otrzymalismy w wyniku rozkladu liczby na czynniki? - skad wiadomo, ze te liczby sa liczbami pierwszymi? • Uczniowie wchodza na strone internetowa (www.szkoly.edu.pl/gim.margonin) i wyszukuja informacje na temat liczb pierwszych: - co to jest sito Eratostenesa? - jaka liczbe nazywamy liczba Mersenne'a ?; - ciekawostki na temat liczb pierwszych. • Nauczyciel tlumaczy sposób wyznaczania NWD z zastosowaniem odejmowania:
Algorytm Euklidesa znajdowania NWD - wersja z odejmowaniem |
Jesli chcesz znalezc Najwiekszy Wspólny Dzielnik dwóch liczb, to od wiekszej z nich odejmuj mniejsza dotad, az obie liczby beda sobie równe. Wynik jest ich najwiekszym wspólnym podzielnikiem. |
Przyklad Obliczmy tym sposobem NWD liczb 24 i 15.
24-15=9 |
Od wiekszej liczby odejmujemy mniejsza. Liczby 24 i 15 przechodza w 15 i 9. Poniewaz nie sa one równe, wykonujemy dalej odejmowanie |
15-9=6 |
Teraz otrzymujemy pare 9 i 6, która dalej nie sklada sie z liczb sobie równych, wiec kontynuujemy odejmowanie. |
9-6=3 |
Para 6 i 3 - odejmujemy dalej |
6-3=3 |
Para 3 i 3 - otrzymalismy równosc, wiec liczba 3 jest najwiekszym wspólnym podzielnikiem liczb 24 i 15. |
• Przypomnienie podstawowych wiadomosci o algorytmach: Budowa algorytmu - Algorytm musi byc przedstawiony w taki sposób aby mógl byc jednoznacznie odczytany i mozna go bylo odpowiednio zastosowac. - Kazdy algorytm zawiera:
- opis danych
- opis wyników
- plan dzialania czyli przetworzenia danych.
- Plan dzialania - przedstawiany jest w postaci ciagu czynnosci, które to musza byc wykonane w okreslonej kolejnosci; - Opis czynnosci wystepujacych w algorytmie nazywamy - instrukcjami procedury. Cechy dobrego algorytmu
Algorytm musi byc:
- poprawny, tzn. dla kazdego poprawnego zestawu danych, po wykonaniu skonczonej liczby czynnosci, prowadzi do poprawnych wyników
- szczególowy, aby wykonawca algorytmu rozumial opisane czynnosci i potrafil je wykonac
- jednoznaczny, tzn. w kazdym przypadku jego zastosowania, dla tych samych danych uzyskamy ten sam wynik
- uniwersalny, aby sluzyl do rozwiazywania pewnej grupy zadan, a nie tylko jednego zadania: np. algorytm jest przepisem na rozwiazanie równania postaci ax+b=0 dla dowolnych wspólczynników a i b, a nie – jednego konkretnego równania, np. 2x+3=0.
• Nauczyciel dzieli grupe na zespoly 2 osobowe. Uczniowie zapisuja algorytm wyznaczania NWD w postaci listy kroków. • Nauczyciel kontroluje prace uczniów w razie potrzeby ukierunkowuje dzialania uczniów.
Przykladowe rozwiazanie zadania:
wyznaczanie NWD:
- dane sa dwie liczby a i b,
- dopóki liczby a i b nie sa sobie równe, powtarzaj krok trzeci w przeciwnym wypadku przejdz do kroku czwartego,
- od wiekszej liczby odejmij mniejsza i te wieksza zastap otrzymana róznica,
- wyprowadz wynik NWD.
Uczniowie porównuja swoje prace. • Uczniowie zamieniaja liste kroków na schemat blokowy /wczesniej przypominamy co to jest „schemat blokowy:” / Pojecie schematu blokowego: - Schemat blokowy - jest to graficzny zapis algorytmu rozwiazania zadania, problemu przedstawiajacy opis i kolejnosc wykonywania czynnosci realizujacych dany algorytm. Opis symboli graficznych stosowanych w schematach blokowych:
Skrzynki START i STOP wskazuja poczatek i koniec kazdego algorytmu. Ze skrzynki START wychodzi tylko jedna droga, do skrzynki STOP wchodzi co najmniej jedno polaczenie. |
W skrzynce instrukcyjnej umieszcza sie polecenia do wykonania ( instrukcje ) - podstawienie, obliczenie, wprowadzenie wartosci. |
W skrzynce warunkowej umieszcza sie warunek, który decyduje o wyborze dalszej drogi postepowania. Ze skrzynki wychodza dwa polaczenia: TAK ( wybierane, gdy warunek jest spelniony ), NIE ( gdy warunek nie jest spelniony ). |
W skrzynce wejscia / wyjscia umieszcza sie wprowadzane dane lub wyprowadzane wyniki. Ze skrzynki wychodzi tylko jedno polaczenie. |
Pojecie – instrukcji algorytmicznej
INSTRUKCJA - nazywamy opis czynnosci wystepujacych w algorytmie ( przyklady z ksiazki - zadzwonienie na numer 999 i wezwanie lekarza do chorego ) - omówienie przykladów .
Rodzaje instrukcji algorytmicznych (prezentacja w PowerPoincie przygotowana przez nauczyciela np.: „Algorytm Euklidesa”)
a). Instrukcje sekwencyjne (liniowe) - kolejnosc instrukcji jedna po drugiej, a wiec instrukcja wykonana w kolejnosci wynikajacej z ich nastepstwa – sekwencji
b). Instrukcje interacyjne (zw. petlami) - sa to instrukcje wielokrotnego powtarzania. Nie zawsze liczbe powtórzen mozna okreslic dokladnie, czesto uzaleznione jest to od spelnienia pewnych warunków.
Schemat blokowy do algorytmu Euklidesa opracowany przez uczniów:
Na schemacie blokowym stosujemy nastepujace symbole: a, b : liczby, dla których poszukujemy NWD Po odczytaniu wartosci liczb a i b rozpoczynamy petle, która przerwie sie, gdy w wyniku dzialania algorytmu liczba a bedzie równa liczbie b. W takim przypadku dowolna z tych liczb jest NWD.
W przeciwnym wypadku jedna z liczb a lub b jest wieksza od drugiej. Odejmujemy wiec liczbe mniejsza od wiekszej i kontynuujemy petle, az do zrównania wartosci a i b. • Badanie efektywnosci algorytmów wyznaczania NWD z zastosowaniem odejmowania – wnioski. • Nauczyciel dzieli grupe na czteroosobowe zespoly. • Zastosowania algorytmu Euklidesa.
Znana jest nastepujaca lamiglówka: Dysponujesz: dwoma czerpakami o pojemnosciach 4 i 6 litrów, pustym pojemnikiem o nieograniczonej pojemnosci i nieograniczona iloscia wody. Podaj sposób napelnienia pojemnika 15 litrami wody, przy czym wode z kranu mozesz wlewac do pojemnika lub wylewac z niego tylko pelnymi czerpakami. • Uczniowie pracuja nad rozwiazaniem zadania. • Prezentacja rozwiazan grup – porównanie z prawidlowym rozwiazaniem.
III. Czesc koncowa: 1. Ocena wkladu pracy. 2. Podsumowanie zajec.
Zdobyte umiejetnosci i kompetencje ucznia: • Umiejetnosc wykorzystania komputera do wielokrotnego wykonywania ciagu instrukcji; • Umiejetnosci przedstawiania algorytmów w postaci schematów blokowych i jednego z jezyków programowania; • Umiejetnosc stosowania powtórzen z warunkiem; • Umiejetnosc pracy w grupie, prezentowania swoich rozwiazan; • Umiejetnosc abstrakcyjnego myslenia, myslenia logicznego i wyciagania wniosków; • Umiejetnosc stosowania metody prób i bledów i kolejnych ulepszen. Literatura: 1. Syslo M.M., Algorytmy, WSiP, Warszawa 1997; 2. Zdzislaw Nowakowski, Witold Sikorski „Informatyka bez tajemnic czesc III programowanie mikrokomputerów”, MIKOM, Warszawa 1997. 3. Strony internetowe: www.szkoly.edu.pl/gim.margonin www.szkoly.edu.pl/gim.margonin/starozyt/euklid.htm, www.matematyka.prx.pl/strona/biografie/euklides.htm
Scenariusz opracował mgr Grzegorz Weber
|